public class Test {
    //斐波那契循环代码/迭代代码(计算速度更快）
    public static int fib1(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        int f1 = 1;
        int f2 = 1;
        int f3 = -1;
        //画图，找规律，移动f1,f2,f3的位置
        for (int i = 3; i <=n ; i++) {
            f3=f1+f2;
            f1=f2;
            f2=f3;
        }
        return f3;
    }

    public static void main(String[] args) {
        System.out.println(fib(1));
        System.out.println(fib(2));
        System.out.println(fib(3));
        System.out.println(fib1(41));
        System.out.println("========");
        System.out.println(fib(41));
    }


    //斐波那契递归代码
    public static int fib (int n){
        if(n == 1|| n == 2){
            return 1;
        }
        return fib(n-1)+fib(n-2);
    }
    public static void main(String[] args) {
        System.out.println(fib(1));
        System.out.println(fib(2));
        System.out.println(fib(3));
        System.out.println(fib(4));
        System.out.println(fib(5));
    }
}
